package algorithm.leetcode.I1to100;

import java.util.*;

/**
 * 思路: 全排列+剪枝
 * 自己写的代码果然有点垃圾
 */

public class Q22 {

    public static void main(String[] args) {
        Q22 q22 = new Q22();
        System.out.println(q22.generateParenthesis(3));
    }

    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        if (n <= 0) return res;
        generateHelper("", n, n);
        return res;
    }

    /**
     * 我对上面大佬的方法理解融合递归的模板 进入这个方法的前提条件是 剩余的右括号比左括号多或者相等,不可能小于
     * 直观理解是,当字符串中左括号比右括号多时,是可以通过在后面添加右括号弥补的,但是反过来是不可以的
     * 正向回溯不check的秘密: 组合成的括号字符串substring(0,k)都满足左括号大于或等于右括号,k为任意的1到字符串长度间(含)的正整数
     * @param str 当前字符串
     * @param left 剩余可用左括号数量
     * @param right 剩余可用右括号数量
     */
    private void generateHelper(String str, int left, int right) {
        if (left == 0 && right == 0) {
            res.add(str);
            return;
        }

        if (right >= left) {
            // 剩余的右括号比左括号多或者相等的情况下,每次都可以添加左括号或者右括号,并根据添加的括号改变向下递归的left和right的值
            // 因为每次只有两种选择,有点像二叉树的展开
            if (left >= 1) generateHelper(str+"(", left-1, right);
            if (right >= 1) generateHelper(str+")", left, right-1);
        }
    }

}
